package 笔试;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

public class 安排会议日程 {
    public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        List<Integer> ans = new LinkedList<>();

        Arrays.sort(slots1, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        Arrays.sort(slots2, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        int m = slots1.length;
        int n = slots2.length;
        int i = 0;
        int j = 0;
        while(i < m && j < n) {
            int start = Math.max(slots1[i][0], slots2[j][0]);
            int end = Math.min(slots1[i][1], slots2[j][1]);
            if(start < end && (end-start) >= duration) {
                ans.add(start);
                ans.add(start+duration);
                return ans;
            }

            if(slots1[i][1] <= slots2[j][1]) {
                i++;
            } else {
                j++;
            }
        }
        return ans;
    }
}
